#include <iostream>

using namespace std;

template<class T>
struct NODE
{
    T data;
    NODE* next;
    NODE* front;
};
template <class T>
class QUEUE
{
public:
    QUEUE()
    {
    queue=(NODE<T> *)new NODE<T>;
    queue->front=NULL;
    queue->next=NULL;
    queue->data=(T)0;
    head=queue;            
    end=queue;
    };

    ~QUEUE();
    bool empty();
    void push(const T &element);
    void pop();
    T front();
    T back();
    void display();
private:
    NODE<T>* queue;
    NODE<T>* head;
    NODE<T>* end;
    T data;
};

template<class T>
QUEUE<T>::~QUEUE()
{
    while(head!=NULL)
    {
        queue=head;
        head=head->next;
        free(queue);
    }
};

template <class T>
bool QUEUE<T>::empty()
{
    if(head==end)
    {
        return true;
    }
    else return false;
};

template <class T>
void QUEUE<T>::push(const T &element)
{
    NODE<T>* temp=(NODE<T>*)new NODE<T>;
    
    temp->data=element;
    temp->front=end;
    end->next=temp;
    temp->next=NULL;
    end=temp;
};

template <class T>
void QUEUE<T>::pop()
{
    queue=head;
    head=head->next;
    free(queue);
};


template <class T>
void QUEUE<T>::display()
{
    if(empty()) 
    {
        cout<<"the queue is empty"<<endl;
    }
    else cout<<"the queue is not empty"<<endl;
    NODE<T>* temp=head->next;
    while(temp!=NULL)
     {
         cout<<temp->data<<" ";
         temp=temp->next;
     };
    cout<<endl;
};

template <class T>
T QUEUE<T>::back()
{
    return end->data;
};

template <class T>
T QUEUE<T>::front()
{
    return head->data;
};

int main()
{
    QUEUE<int> a;
    for(int i=1;i<=5;i++)
    {
        a.push(i*3);
    }

    a.display();

    a.pop();
    a.display();

    system("pause");
    return 0;
}


